package complexdatastructure.multidatastructure;

import java.util.HashMap;
import java.util.Map;

/**
 * @Classname : LRUCache
 * @Description : <a href="https://leetcode.cn/problems/lru-cache/">146. LRU 缓存</a>
 * @Author : chentianyu
 * @Date 2023/2/10 21:28
 */


public class LRUCache {
    // 定义双向链表节点
    class DLinkedList {
        int key;
        int value;
        DLinkedList pre;
        DLinkedList next;

        public DLinkedList() {}
        public DLinkedList(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    // 定义链表头和尾节点
    private DLinkedList head;
    private DLinkedList tail;
    // 定义辅助查询Map
    private Map<Integer, DLinkedList> map;
    // 定义链表容量
    private int capacity;

    public LRUCache(int capacity) {
        this.head = new DLinkedList();
        this.tail = new DLinkedList();
        this.head.next = this.tail;
        this.tail.pre = this.head;
        this.map = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;

        DLinkedList cur = map.get(key);
        removeNode(cur);  // 链表删除当前节点
        addNodeToHead(cur);  // 当前节点插入链表头部
        return cur.value;
    }

    public void put(int key, int value) {
        // 若key已经存在处理方式一：相当于更新对应节点value并进行一次查询
        if (map.containsKey(key)) {
            map.get(key).value = value;
            get(key);
            return;
        }
//        // 若key已经存在处理方式二：把当前已存在重复key的信息删除
//        if (map.containsKey(key)) {
//            removeNode(map.get(key));
//            map.remove(key);
//        }

        // 若链表容量已满，移出尾部节点
        if (map.size() == this.capacity) {
            map.remove(tail.pre.key);  // 【因此链表节点需要存一下key】
            removeNode(tail.pre);
        }

        // 定义当前节点并插入链表头部
        DLinkedList cur = new DLinkedList(key, value);
        addNodeToHead(cur);
        map.put(key, cur);
    }

    // 链表删除节点
    private void removeNode(DLinkedList node) {
        if (node.pre == null || node.next == null) return;
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.pre = null;
        node.next = null;
    }

    // 节点插入链表头部
    private void addNodeToHead(DLinkedList node) {
        DLinkedList next = head.next;
        head.next = node;
        next.pre = node;
        node.pre = head;
        node.next = next;
    }
}
